package cn.itcast.day04.demo01;

import com.interview.javabasic.JUC.A;

import javax.swing.tree.TreeNode;
import java.net.Socket;
import java.util.*;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2020/8/26

*/
/*若一个数出现三次，则其对应的二进制数每一位相加必为3或0。
统计数组中所有元素的每一位，若为3的倍数，所求数的该二进制位对3取余为0，否则为1。
**/
public class Solution {
    ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) {
        Solution S = new Solution();
        String s = "\"O;.'oD:e5Y4A Z00'!2;n'lnN?xO'JB,vkK`z:JH2,9'a!r4:OaZ8y t`I`,'n'0 CKO'? yYidqrizswunige5K B47J'6t.;zPM;'?Bi?0s'n'H`NvppvN`H'n's0?iB?';JPz;.t6'J74B K5eginuwszirqdiYy ?'OKC 0'n',`I`t y8ZaO:4r!a'9,2HM:z`Kkv,BJ'Ox?Nnl'n;2!'00Z A4Y5e:Do'.;O\"";
        String abcd = S.isABCD(s);
        System.out.println(isPalindrome(abcd));
    }



    //截取字母
    public String isABCD(String s){
        StringBuffer sb = new StringBuffer();
        for (char c : s.toCharArray()) {
            if (c>='a'&&c<='z'){
                sb.append(c);
            }
        }
        String res = sb.toString().toLowerCase();

        return res;
    }

    public ArrayList<ArrayList<String>> findLadders(String start, String end, ArrayList<String> dict) {
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        ArrayList<String> tmp = new ArrayList<>();
        findOneSoultions(start, end, dict,0, tmp,result);
        int min = result.get(0).size();
        ArrayList<ArrayList<String>> len = new ArrayList<>();
        for (ArrayList<String> strings : result) {
            if (min > strings.size()){
                len.clear();
                len.add(strings);
            }
            if (min == strings.size()){
                len.add(strings);
            }
        }
        return len;
    }

    public ArrayList<String> findOneSoultions(String start,String end,ArrayList<String> dict,int p, ArrayList<String> tmp,ArrayList<ArrayList<String>> result){
        if (simOne(start,end)){
            tmp.add(start);
            tmp.add(end);
            result.add(tmp);
            return tmp;
        }
        for (int i = p; i < dict.size(); i++) {
            if (simOne(start,dict.get(i))){
                ArrayList list = new ArrayList(tmp);
                tmp.add(start);
                findOneSoultions(dict.get(i),end,dict,i+1,tmp,result);
                tmp = list;
            }
        }
        /*************************************************************************/
        return null;
    }

    public int ladderLength(String start, String end, HashSet<String> dict) {
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        ArrayList<String> tmp = new ArrayList<>();
        ArrayList<String> dic = new ArrayList<>(dict);
        findOneSoultions(start, end, dic,0, tmp,result);
        if (result.size()==0){
            return 0;
        }
        int min = result.get(0).size();
        ArrayList<ArrayList<String>> len = new ArrayList<>();
        for (ArrayList<String> strings : result) {
            if (min > strings.size()){
                len.clear();
                len.add(strings);
                min = strings.size();
            }
            if (min == strings.size()){
                len.add(strings);
            }
        }
        return min;
    }

        public boolean simOne(String s1,String s2){
            int len = s1.length();
            int count = 0;
            for (char c : s1.toCharArray()) {
                if (s2.contains(c+"")){
                    count++;
                }
            }
            if (count == len - 1||count == len){
                return true;
            }else{
                return false;
            }
        }
    public boolean setway(int[][] map,int i,int j,int k){
        if (map[k-1][k-1] == 2){
            return true;
        }else{
            if (map[i][j] == 1){
                //表示这个没人走
                map[i][j] = 2;
                if (setWay(map,i+1,j)){
                    return true;
                }else if (setWay(map,i,j+1)){
                    return true;
                }else if (setWay(map,i-1,j)){
                    return true;
                }else if (setWay(map,i,j-1)){
                    return true;
                }else{
                    map[i][j] = 3;
                    return false;
                }
            }else {
                return false;
            }
        }
    }

    public int longestConsecutive (int[] num) {
        // write code here
        Map<Integer,Boolean> map = new HashMap<>();
        int max = -1;
        int count = 0;
        for (int i : num) {
            map.put(i,false);
        }
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()){
            Integer next = iterator.next();
            if (map.get(next)){
                continue;
            }
            int tmp = next;
            while (map.containsKey(next)){
                map.put(next,true);
                next = next + 1;
                count++;
            }
            next = tmp - 1;
            while (map.containsKey(next)){
                map.put(next,false);
                next = next - 1;
                count++;
            }
            if (count>max){
                max = count;
            }
            count = 0;
        }
        return max;
   }


    public void solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            d_f_s(board,i,0);
            d_f_s(board,i,board[i].length-1);
        }
        for (int i = 0; i < board[0].length; i++) {
            d_f_s(board,0,i);
            d_f_s(board,board.length-1,i);
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j]=='*'){
                    board[i][j] = 'O';
                }
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void d_f_s(char[][] board,int row,int col){
        if (board[row][col] == 'O') {
            if (row > 1){
                d_f_s(board,row-1,col);
            }
            if (col > 1){
                d_f_s(board,row,col-1);
            }
            if (row<board.length){
                d_f_s(board,row+1,col);
            }
            if (col < board[row].length){
                d_f_s(board,row,col+1);
            }
        };

    }

    public static boolean setWay(int[][] map,int i,int j){
        if (i == map.length){//通路已经找到了
            return true;
        }else{
            if (map[i][j]==0){
                //当前的这个路还没有走过。
                map[i][j] = 2;//暂时假定该点是可以走通的。
                if (setWay(map,i+1,j)){//向下走
                    return true;
                }else if (setWay(map,i,j+1)){
                    //向右走
                    return true;
                }else if (setWay(map,i-1,j)){
                    return true;
                }else if (setWay(map,i,j-1)){
                    return true;
                }else {
                    //说明该点走不通，死路
                    map[i][j] = 3;
                    return false;
                }

            }else{//map[i][j]!=0,1,2,3
                return false;
            }
        }
    }

    public ArrayList<ArrayList<String>> partition (String s) {
        // write code here
        dfs(s,"",s.length());
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        for (String s1 : list) {
            String[] s2 = s1.split(" ");
            ArrayList<String> tmp = new ArrayList<String>(Arrays.asList(s2));
            result.add(tmp);
        }
        return result;

    }

    public void dfs(String s,String str,int index){
        if (index <=0) {
            if (str.length() > 0) {
                list.add(str.substring(0, str.length() - 1));
            }
        }
            for (int i = index; i >=0 ; i--) {
                String sub = s.substring(i,index);
                if (isPalindrome(sub)){
                    String tmp = str;
                    str = sub + " " + str;
                    dfs(s,str,i);
                    str = tmp;
                }

            }

    }

    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            dp[i] = isPalindrome(s.substring(0, i + 1)) ? 0 : i;
            if (dp[i] != 0) { //dp[i] = 0时不需要内循环
                for (int j = i; j > 0; j--) {
                    if (isPalindrome(s.substring(j, i + 1))) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[s.length() - 1];
    }

    private static boolean isPalindrome(String s) {
        int begin = 0;
        int end = s.length() - 1;
        while (begin < end) {
            if (s.charAt(begin++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }

    public int canCompleteCircuit (int[] gas, int[] cost) {
        // write code here
        int p = 0;
        int count = 1;
        int sum = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while (count <= gas.length&&list.size()!=gas.length+1){
            for (int i = 0; i <= gas.length; i++) {
                sum += gas[p];
                list.add(p);
                sum -= cost[p];
                if (sum < 0){
                    p = count;
                    count++;
                    list.clear();
                    sum = 0;
                    break;
                }
                if (p==gas.length-1){
                    p = 0;
                }else{
                    p++;
                }
                if (list.size()==gas.length+1){
                    break;
                }
            }
        }
        if (list.size()==gas.length+1){
            return count-1;
        }else {
            return -1;
        }


    }

    public int candy (int[] ratings) {
        // write code here
        int[] candy = new int[ratings.length];
        for (int i = 0; i < candy.length; i++) {
            candy[i] = 1;
        }
        for (int i = 0; i < ratings.length-1; i++) {
            if (ratings[i+1] > ratings[i]){
                candy[i+1] = candy[i] + 1;
            }
        }
        for (int i = ratings.length-1; i >0 ; i--) {
            if (ratings[i-1]>ratings[i] && candy[i-1]<=candy[i]){
                candy[i-1] = candy[i] + 1;
            }

        }
        int sum = 0;
        for (int i = 0; i < candy.length; i++) {
            sum += candy[i];
        }
        return sum;
    }

    public int singleNumber(int[] A) {
        int result=0;
        for(int i=0;i<32;++i){
            int bits=0;
            for(int j=0;j<A.length;++j){
                bits+=(A[j]>>i)&1;//依次获取元素的每一位，并将数组元素相同位相加
            }
            result|=(bits%2)<<i;
        }
        return result;
    }

}
